1. Field of the Invention
The present invention relates to techniques for improving computer system performance. More specifically, the present invention relates to a method and apparatus that provides selective versioning of memory objects to support space and time dimensional execution of a computer program.
2. Related Art
As increasing semiconductor integration densities allow more transistors to be integrated onto a microprocessor chip, computer designers are investigating different methods of using these transistors to increase computer system performance. Some recent computer architectures exploit xe2x80x9cinstruction level parallelism,xe2x80x9d in which a single central processing unit (CPU) issues multiple instructions in a single cycle. Given proper compiler support, instruction level parallelism has proven effective at increasing computational performance across a wide range of computational tasks. However, inter-instruction dependencies generally limit the performance gains realized from using instruction level parallelism to a factor of two or three.
Another method for increasing computational speed is xe2x80x9cspeculative executionxe2x80x9d in which a processor executes multiple branch paths simultaneously, or predicts a branch, so that the processor can continue executing without waiting for the result of the branch operation. By reducing dependencies on branch conditions, speculative execution can increase the total number of instructions issued.
Unfortunately, conventional speculative execution typically provides a limited performance improvement because only a small number of instructions can be speculatively executed. One reason for this limitation is that conventional speculative execution is typically performed at the basic block level, and basic blocks tend to include only a small number of instructions. Another reason is that conventional hardware structures used to perform speculative execution can only accommodate a small number of speculative instructions.
What is needed is a method and apparatus that facilitates speculative execution of program instructions at a higher level of granularity so that many more instructions can be speculatively executed.
One embodiment of the present invention provides a system that facilitates space and time dimensional execution of computer programs through selective versioning of memory elements located in a system heap. The system includes a head thread that executes program instructions and a speculative thread that simultaneously executes program instructions in advance of the head thread with respect to the time dimension of sequential execution of the program. The collapsing of the time dimensions is facilitated by expanding the heap into two space-time dimensions, a primary dimension (dimension zero), in which the head thread operates, and a space-time dimension (dimension one), in which the speculative thread operates. In general, each dimension contains its own versions of objects, and objects created by the thread operating in the dimension. The head thread generally accesses a primary version of a memory element and the speculative thread generally accesses a corresponding space-time dimensioned version of the memory element. During a write by the head thread, the system performs the write to all dimensions of the memory element. Note that if the dimensions are collapsed at this address a single update will update all space-time dimensions. It also checks status information associated with the memory element to determine if the memory element has been read by the speculative thread. If so, the system causes the speculative thread to roll back so that the speculative thread can read a result of the write operation.
In a variation on the above embodiment, during a read operation by the speculative thread, the thread first updates status information associated with the memory element to indicate that the memory element has been read by the speculative thread. Next, the thread reads the space-time dimensioned version of the memory element. If the space-time dimensions are collapsed into the primary version, the thread reads the primary version. If not, the thread reads the space-time dimensioned version.
In a variation on the above embodiment, during a write operation by the speculative thread to a memory element, the thread determines if the space-time dimensions are collapsed at the memory element. If so, the thread creates a new version of the memory element for the space-time dimension. Next, the thread performs the write operation to the memory element in the space-time dimension.
In a variation on the above embodiment, the system performs a join operation between the head thread and the speculative thread when the head thread reaches a point in the program where the speculative thread began executing. The join operation causes state associated with the speculative thread to be merged with state associated with the head thread and collapsing of the space-time dimensions of the heap.
Thus, the present invention can be thought of as speculating at a higher level than traditional speculative execution. At this higher level, the system speculates on the state of the heap; not on the outcome of a branch instruction or an instruction execution.